package main

import (
	"fmt"
	"strconv"
)

/*
把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:
输入: [10,2]
输出: "102"

示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
*/

//快排 （eg：比较 30 9 和 9 30 谁大）
func minNumber(nums []int) string {
	//quick1(nums, 0, len(nums)-1)
	quick2(nums)
	var res string
	for _, v := range nums {
		res = res + strconv.Itoa(v)
	}
	return res
}

func quick1(num []int, start, end int) {
	if start < end {
		i, j := start, end
		key := num[(start+end)/2]
		for i <= j {
			for compare(num[i], key) {
				i++
			}
			for compare(key, num[j]) {
				j--
			}
			if i <= j {
				num[i], num[j] = num[j], num[i]
				i++
				j--
			}
		}
		if start < j {
			quick1(num, start, j)
		}
		if end > i {
			quick1(num, i, end)
		}
	}
}

func quick2(n []int) {
	if len(n) <= 1 {
		return
	}
	l, r, key := 0, len(n)-1, n[0]
	for i := 1; i <= r; {
		if compare(key, n[i]) { //n[i]+key > key+n[i] //因为总数要最小 就把大的放到后面
			n[i], n[r] = n[r], n[i]
			r--
		} else {
			n[i], n[l] = n[l], n[i]
			i++
			l++
		}
	}
	quick2(n[:l])
	quick2(n[l+1:])
}

func compare(a, b int) bool {
	str1 := fmt.Sprintf("%d%d", a, b)
	str2 := fmt.Sprintf("%d%d", b, a)
	if str1 < str2 { //ab<ba
		return true
	}
	return false
}

func main() {
	fmt.Println(minNumber([]int{3, 30, 34, 5, 9}))
}
